package com.mango.data.structure.graph;

import java.util.*;

/**
 * 图 - 邻接表实现
 * @Author: mango
 * @Date: 2022/4/24 11:36 下午
 */
public class Graph {
    // 顶点集 - 邻接表
    public HashMap<String,Vertex> vertexs;
    // 边集
    public Set<Edge> edges;

    public Graph() {
        this.vertexs = new HashMap<>();
        this.edges = new HashSet<>();
    }

    /**
     * 图的dfs遍历，深度优先遍历
     * 用栈实现
     * @param vertex 初始顶点
     * @return
     */
    public Set<Vertex> dfs(Vertex vertex){
        Set<Vertex> result = new LinkedHashSet<>();
        Stack<Vertex> stack = new Stack<>();
        Set<Vertex> pass = new HashSet<>();
        // 将初始顶点加入到栈和路过的集合pass里
        stack.add(vertex);
        pass.add(vertex);
        result.add(vertex);
        // 处理栈
        while (!stack.isEmpty()){
            Vertex cur = stack.pop();
            // 处理相邻的顶点
            for(Vertex next : cur.nexts){
                // 不在pass里的
                if(!pass.contains(next)){
                    // 记录到pass里
                    pass.add(next);
                    // 先将原来节点压入到栈里
                    stack.add(cur);
                    stack.add(next);
                    // 找到一个就退出
                    result.add(next);
                    break;
                }
            }
        }
        return result;
    }

    /**
     * 图的宽度优先遍历，bfs，用队列
     * @param vertex 初始顶点
     * @return
     */
    public Set<Vertex> bfs(Vertex vertex){
        Set<Vertex> result = new LinkedHashSet<>();
        Queue<Vertex> queue = new LinkedList<>();
        Set<Vertex> pass = new HashSet<>();
        queue.offer(vertex);
        pass.add(vertex);
        // 处理队列
        while (!queue.isEmpty()){
            Vertex cur = queue.poll();
            result.add(cur);
            // 处理相邻节点
            for(Vertex next : cur.nexts){
                if(!pass.contains(next)){
                    queue.offer(next);
                    pass.add(next);
                }
            }
        }
        return result;
    }

    /**
     * 图的topo排序算法
     * 1. 找到入度为0的节点加入到队列
     * 2. 取出队列里的点，消除相邻点的影响
     * @return 拓扑序列；
     *          null，则说明不是有向无环图
     */
    public Set<Vertex> kahnPololog(){
        Set<Vertex> result = new LinkedHashSet<>();
        Queue<Vertex> inZeroQueue = new LinkedList<>();
        // 记录顶点的入度
        Map<Vertex,Integer> inMap = new HashMap<>();
        for(Vertex vertex : vertexs.values()){
            inMap.put(vertex,vertex.in);
            // 如果入度为0加入到队列
            if(vertex.in == 0){
                inZeroQueue.offer(vertex);
            }
        }
        // 处理如多为0的队列
        while (!inZeroQueue.isEmpty()){
            Vertex cur = inZeroQueue.poll();
            result.add(cur);
            // 消除掉该顶点相邻的点的入度影响
            for(Vertex next : cur.nexts){
                inMap.put(next,inMap.get(next) - 1);
                // 如果入度为零，则加入到队列
                if(inMap.get(next) == 0){
                    inZeroQueue.offer(next);
                }
            }
        }
        // 如果result的大小等于图里顶点数量，则说明拓扑排序成功，图是有向无环的，反之返回null
        return result.size() == vertexs.size() ? result : null;
    }

    /**
     * prim算法求图的最小生成树（加点法）
     * 1. 从图里一个顶点出发，找该点相邻的最小边edge加入到小根堆
     * 2. 取出小根堆里的边edge,判断edge的to顶点是否已经经过，没有则找到最小边，有则跳过
     * 3. 将edge.to顶点的相邻边加入到小根堆里，循环2，3步骤
     * @return 最小边集合
     */
    public Set<Edge> primMST(){
        Set<Edge> result = new LinkedHashSet<>();
        // 小根堆，使用边的权值排序
        PriorityQueue<Edge> edgePQ = new PriorityQueue<>(((o1, o2) -> o1.weight - o2.weight));
        Set<Vertex> pass = new HashSet<>();
        // 加上循环是为了防止森林场景
        for(Vertex vertex : vertexs.values()){
            // 该顶点没有在pass里
            if(!pass.contains(vertex)) {
                // 将顶点加入到pass里，表示经过该顶点
                pass.add(vertex);
                // 将该顶点的相邻的边加入到堆里
                for (Edge edge : vertex.edges) {
                    edgePQ.offer(edge);
                }
                // 取出该节点最小边
                while (!edgePQ.isEmpty()) {
                    Edge edge = edgePQ.poll();
                    // 没有经过edge.to顶点
                    if (!pass.contains(edge.to)) {
                        // 记录到边集合里
                        result.add(edge);
                        // 将edge.to顶点加入到pass里
                        pass.add(edge.to);
                        // 将edge.to顶点相邻的边加入到小根堆里
                        for (Edge next : edge.to.edges) {
                            if (!edgePQ.contains(next)) {
                                edgePQ.offer(next);
                            }
                        }
                    }
                }
            }
        }
        return result;
    }

    /**
     * kruskal算法求图的最小生成树（加边法）
     * 1. 初始化map，key=顶点，value=包含自己顶点的集合
     * 2. 建立小根堆，按图里所有边的权值排序
     * 3. 依次取出堆里的最小边，判断边的from和to顶点是否在同一个集合
     * 4. 如果不在就记录边到结果集合里，并且将from和to顶点合并到同一个集合
     * @return 最小边集合
     */
    public Set<Edge> kruskalMST(){
        Set<Edge> result = new LinkedHashSet<>();
        SimpleSet simpleSet = new SimpleSet(vertexs.values());
        // 小根堆，使用边的权值排序
        PriorityQueue<Edge> edgePQ = new PriorityQueue<>(((o1, o2) -> o1.weight - o2.weight));
        for(Edge edge : edges){
            edgePQ.offer(edge);
        }
        while (!edgePQ.isEmpty()){
            Edge edge = edgePQ.poll();
            // 边的from和to不在同一个集合里
            if(!simpleSet.isSameSet(edge.from,edge.to)){
                // 合并
                simpleSet.union(edge.from,edge.to);
                result.add(edge);
            }
        }
        return result;
    }

    /**
     * dijkstra算法求单元最小路径,适用范围：没有累加为负数的环
     * 1. 初始化路径表distanceMap,from顶点到各个顶点的距离
     * 2. 在路径表distanceMap找没有被锁定（不在lockSet)的最小顶点
     * 3. 最小顶点不为空，则处理最小顶点的相邻边，记录边的to顶点的最小距离到记录表里
     * 4. 处理完后将最小顶点加入到lockSet里锁定
     * 5. 找下一个最小顶点，循环步骤3执行
     * @param from 开始顶点
     * @return key=顶点，value=from顶点到各个顶点的最小路径
     */
    public Map<Vertex,Integer> dijkstra(Vertex from){
        // 记录最小路径的map
        Map<Vertex,Integer> distanceMap = new LinkedHashMap<>();
        // 记录自己为零
        distanceMap.put(from,0);
        Set<Vertex> lockSet = new HashSet<>();
        // 在distanceMap里找到未被锁定的的最小路径的顶点
        Vertex theMin = findMin(distanceMap,lockSet);
        while(theMin != null){
            // 原来记录的最小路径
            Integer distance = distanceMap.get(theMin);
            // 处理最小顶点的边
            for(Edge edge : theMin.edges){
                // edge.to顶点没有被记录在distanceMap里的
                if(!distanceMap.containsKey(edge.to)){
                    distanceMap.put(edge.to,distance + edge.weight);
                }else{
                    // 已经记录的则更新最小值
                    distanceMap.put(edge.to,Math.min(distanceMap.get(edge.to),distance + edge.weight));
                }
            }
            // 处理完最小顶点的相邻边后，加入锁定
            lockSet.add(theMin);
            // 继续找下一个最小顶点处理
            theMin = findMin(distanceMap,lockSet);
        }
        return distanceMap;
    }

    /**
     * 在distanceMap里找到未被锁定的（不在lockSet)里的最小路径的顶点
     * @param distanceMap 路径记录表
     * @param lockSet 锁定的顶点集合
     * @return 路径最小的点
     */
    private Vertex findMin(Map<Vertex, Integer> distanceMap, Set<Vertex> lockSet) {
        Vertex vertex = null;
        int min = Integer.MAX_VALUE;
        for(Vertex v : distanceMap.keySet()){
            if(!lockSet.contains(v) && min > distanceMap.get(v)){
                vertex = v;
                min = distanceMap.get(v);
            }
        }
        return vertex;
    }

    /**
     * 从数组场景创建图
     * @param data eg,{{1,3,2},{2,3,3}}
     *             表示  从顶点1到顶点3有权值为2的边；
     *                  从顶点2到顶点3有权值为3的边
     * @param direct true为有向，false为无向
     * @return
     */
    public static Graph createGraph(int[][] data,boolean direct){
        Graph graph = new Graph();
        for(int i=0;i<data.length;i++){
            String from = data[i][0] + "";
            String to = data[i][1] + "";
            Integer weight = data[i][2];
            // 将from顶点和to顶点加入到图里
            if(!graph.vertexs.containsKey(from)){
                graph.vertexs.put(from,new Vertex(from));
            }
            if(!graph.vertexs.containsKey(to)){
                graph.vertexs.put(to,new Vertex(to));
            }
            // 从图里获取from和to顶点
            Vertex fromVertex = graph.vertexs.get(from);
            Vertex toVertex = graph.vertexs.get(to);
            // 创建从from顶点到to顶点的边
            Edge edge = new Edge(weight,fromVertex,toVertex);
            // from顶点的出度+1，to顶点的入度+1
            fromVertex.out++;
            toVertex.in++;
            // 将to顶点加入到from顶点里的nexts里
            fromVertex.nexts.add(toVertex);
            // 将边加入到from顶点的边集里
            fromVertex.edges.add(edge);
            // 将边加入到图里
            graph.edges.add(edge);
            // 无向
            if(!direct){
                Edge reverseEdge = new Edge(weight,toVertex,fromVertex);
                fromVertex.in++;
                toVertex.out++;
                toVertex.nexts.add(fromVertex);
                toVertex.edges.add(reverseEdge);
                graph.edges.add(reverseEdge);
            }
        }
        return graph;
    }

    /**
     * 从箭头数组场景创建图
     * @param arrows eg, 自主编号
     *             {
     *             ">>v", 1,2,3
     *             "v^<", 4,5,6
     *             "<><"  7,8,9
     *             }
     *             表示  从顶点1到顶点2有边；顶点2到顶点3有边；顶点3到顶点6有边
     *                  顶点4到顶点7有边；顶点5到顶点2有边；顶点6到顶点5有边
     *                  顶点8到顶点9有边；顶点9到顶点8有边
     * @param direct true为有向，false为无向
     * @return
     */
    public static Graph createGraphFromArrowString(String[] arrows,boolean direct){
        Graph graph = new Graph();
        int row = arrows.length;
        int col = arrows[0].length();
        // 设置上下左右的坐标规则
        Map<Character,int[]> ruleMap = new HashMap<>();
        ruleMap.put('^',new int[]{-1,0});
        ruleMap.put('v',new int[]{1,0});
        ruleMap.put('<',new int[]{0,-1});
        ruleMap.put('>',new int[]{0,1});
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                String from = (i * col + j + 1) + "";
                int[] rule = ruleMap.get(arrows[i].charAt(j));
                int nextI = i + rule[0];
                int nextJ = j + rule[1];
                String to = (nextI * col + (nextJ + 1)) + "";
                // 无权，默认为0
                Integer weight = 0;
                // 判断to点的坐标在合法范围内
                if(nextI >=0 && nextI < row && nextJ >=0 && nextJ < col){
                    // 将from顶点和to顶点加入到图里
                    if(!graph.vertexs.containsKey(from)){
                        graph.vertexs.put(from,new Vertex(from));
                    }
                    if(!graph.vertexs.containsKey(to)){
                        graph.vertexs.put(to,new Vertex(to));
                    }
                    // 从图里获取from和to顶点
                    Vertex fromVertex = graph.vertexs.get(from);
                    Vertex toVertex = graph.vertexs.get(to);
                    // 创建从from顶点到to顶点的边
                    Edge edge = new Edge(weight,fromVertex,toVertex);
                    fromVertex.out++;
                    toVertex.in++;
                    // 将to顶点加入到from顶点里的点集nexts里
                    fromVertex.nexts.add(toVertex);
                    // 将边加入到from顶点的边集里
                    fromVertex.edges.add(edge);
                    // 将边加入到图里
                    graph.edges.add(edge);
                    // 无向
                    if(!direct){
                        Edge reverseEdge = new Edge(weight,toVertex,fromVertex);
                        fromVertex.in++;
                        toVertex.out++;
                        toVertex.nexts.add(fromVertex);
                        toVertex.edges.add(reverseEdge);
                        graph.edges.add(reverseEdge);
                    }
                }
            }
        }
        return graph;
    }
}

// 顶点
class Vertex{
    // 名称，值
    public String value;
    // 入度
    public Integer in;
    // 出度
    public Integer out;
    // 相邻的顶点集合
    public Set<Vertex> nexts;
    // 边集合
    public Set<Edge> edges;

    public Vertex(String value) {
        this.value = value;
        this.in = 0;
        this.out = 0;
        this.nexts = new HashSet<>();
        this.edges = new HashSet<>();
    }
}
// 边
class Edge{
    // 权重
    public int weight;
    // 出发顶点
    public Vertex from;
    // 到达顶点
    public Vertex to;
    public Edge(int weight, Vertex from, Vertex to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}
// 简单集合，替代并查集，提供判断2个顶点是否在同一个集合的方法和合并2个顶点到同一个集合的方法
class SimpleSet{
    private Map<Vertex,Set<Vertex>> vertexSetMap;
    // 初始化map,key=顶点，value=包含自己顶点的set
    public SimpleSet(Collection<Vertex> vertexs){
        vertexSetMap = new HashMap<>();
        for(Vertex vertex : vertexs){
            Set<Vertex> set = new HashSet<>();
            set.add(vertex);
            vertexSetMap.put(vertex,set);
        }
    }

    /**
     * 判断2个顶点在同一集合
     * @param from 开始顶点
     * @param to 结束顶点
     * @return 在同一个集合里返回true，反之返回false
     */
    public boolean isSameSet(Vertex from,Vertex to){
        return vertexSetMap.get(from) == vertexSetMap.get(to);
    }

    /**
     * 合并2个顶点到同一个集合
     * @param from 开始顶点
     * @param to 结束顶点
     */
    public void union(Vertex from,Vertex to){
        Set<Vertex> fromSet = vertexSetMap.get(from);
        fromSet.addAll(vertexSetMap.get(to));
        vertexSetMap.put(from,fromSet);
        for(Vertex next : vertexSetMap.get(to)){
            vertexSetMap.put(next,fromSet);
        }
    }
}
